# 8/100 滑动窗口-无重复字符的最长子串
# leetcode第15题: https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/16
from leetcode import test


def lengthOfLongestSubstring(s: str) -> int:
    if len(s) == 0:
        return 0
    max_win = 1
    start = 0
    for i in range(len(s)):
        window_size = 1
        if start + max_win > len(s):
            return max_win
        while s[start + window_size:start + 1 + window_size] not in (s[start:start + window_size]):
            window_size += 1
            max_win = max(max_win, window_size)
        start += 1 + s[start:start + window_size].index(s[start + window_size:start + 1 + window_size])
    return max_win


def lengthOfLongestSubstring_std(s: str) -> int:
    # 哈希集合，记录每个字符是否出现过
    occ = set()
    n = len(s)
    # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans = -1, 0
    for i in range(n):
        if i != 0:
            # 左指针向右移动一格，移除一个字符
            occ.remove(s[i - 1])
        while rk + 1 < n and s[rk + 1] not in occ:
            # 不断地移动右指针
            occ.add(s[rk + 1])
            rk += 1
        # 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    return ans


def lengthOfLongestSubstring_swin(s: str) -> int:
    n = len(s)
    if n < 2:
        return n
    max_len = 0
    start = 0  # 表示滑动窗口开始的位置
    for end in range(1, n):
        win_str = s[start:end]
        c = s[end]
        if c in win_str:
            # 不需要写 if 语句来判断大小
            max_len = max(max_len, end - start)
            start += win_str.index(c) + 1
    return max(max_len, n - start)


if __name__ == '__main__':
    s1 = "abcabcbb"
    s2 = "bbbbb"
    s3 = "pwwkew"
    s4 = ""
    s5 = " "
    s6 = "ckilbkd"
    s7 = "ggububgvfk"

    inp = [{"s": s1}, {"s": s2}, {"s": s3}, {"s": s4}, {"s": s5}, {"s": s6}, {"s": s7}, ]
    out = [3, 1, 3, 0, 1, 5, 6]
    test.test_function(lengthOfLongestSubstring, inp, out, times=1000)
    test.test_function(lengthOfLongestSubstring_std, inp, out, times=1000)
    test.test_function(lengthOfLongestSubstring_swin, inp, out, times=1000)
